Information network systems continue to proliferate. Typically network data is transferred in data structures referred to as "packets." A packet can travel through network according to information included in a portion of the packet referred to as a "header." Network switches and/or routers can receive packets, extract information from the packet header, and process the packet according to the extracted information. Network header information can establish, to name just a few possible examples, the destination of a packet and/or the manner in which a packet should be transmitted.
Packet routing and/or switching typically utilizes a matching function. In a matching function, a header field will be compared to a number of entries. In the event the field (or a portion of the field) matches an entry, a match indication will be generated. The match indication can be used to generate particular processing information for the packet.
Routing and switching functions can be performed by general-purpose processors that run a routing algorithm. Such an approach can result in limited throughput of data packets, be expensive in terms of component cost, and require considerable area to implement when implemented as one or more integrated circuits.
One way to address the need for faster routers/network switches is to fabricate an integrated circuit that is specialized to perform routing/switching tasks. Such application specific integrated circuits (ASICs) are designed to perform particular routing functions such as a matching function in conjunction with a random access memory (RAM). Unfortunately, because ASICs are custom manufactured products, they can also be expensive to manufacture.
One type of device that is particularly suitable for matching functions is a content addressable memory (CAM) (also referred to as an "associative memory"). A CAM can include a number of data storage locations, each of which can be accessed by a corresponding address. The order in which the data values are stored varies according to the type of CAM. As just one example, in a typical "binary" CAM, data can be stored in the first available "empty" location. Empty locations can be distinguished from "full" (or valid) locations by a status bit associated with each storage location.
Valid locations in a binary CAM can be addressed according to the contents (data values) that they store. In a typical binary CAM matching function, a comparand value (which can be a header field or a portion thereof) can be loaded into a comparand register. The comparand value can then be compared to the data values within each valid location of the conventional binary CAM. In the event the value within the comparand register matches a value of a storage location, a match signal for the matching storage location will be generated. In the event there is more than one match, one match from the multiple matches may be selected according to predetermined priority criteria. The match indication can then be used to access other information (such as routing or packet processing information, as just two examples).
In some configurations, a match indication can be provided to an encoder that can generate an address value. An address value can be used to access associated data. In other configurations, a match line can be coupled to conventional random access memory (RAM) and/or read-only-memory (ROM) cells. Such arrangements can require two different types of memory cell arrays, or even two different integrated circuit devices. This can be costly and bulky to implement.
In yet other configurations, a binary CAM can include binary CAM cells, a portion of which function as binary CAM cells and another portion of which have their respective compare functions disabled, and thus function solely as RAM cells. The RAM cells can provide associated data for the binary CAM cells. While such an approach can provide CAM cells and associated data, ternary match operations (discussed below) are not possible. Further, compare circuitry is essentially wasted in those cells that function solely as RAM cells.
By providing for the simultaneous comparison of a comparand word value (a row of comparand bit values) with a number of data words, a rapid match function can be accomplished with a binary CAM.
One drawback to conventional binary CAMs is that matching functions are typically performed on data values having a fixed number of bits. Unfortunately, many routing and switching functions can require matching a comparand value to data values having variable bit lengths. One such variable length compare operation is a longest prefix matching operation.
An example of longest prefix matching operation will be described below. Two data values (data0 and data1) are set forth. The data values (data0 and data1) are binary values having portions that can be compared to a comparand value (shown as either a 0 or 1). In addition, the data values (data0 and data1) have portions that do not have to be matched. These "non-match" portions are represented by a series of Xs. It is understood that each X could be a 0 or 1 but is represented by an X because the digit should not be compared with a comparand value.
______________________________________ 11110000 10XXXXXX XXXXXXXX XXXXXXXX (data 0) 11110000 10010101 100XXXXX XXXXXXXX (data 1) ______________________________________
For the example of the data values set forth above, if the following comparand value is applied:
______________________________________ 11110000 10010101 10010000 11010001 (comparand). ______________________________________
Both data values can result in a match indication. It is preferred that the data 1 value match indication have priority as it provides the longest prefix match.
One type of device that can be particularly suitable for longest prefix matching is a "ternary" or "tertiary" CAM. In a conventional ternary CAM, a mask bit is provided for each data bit. When the mask bit has a first predetermined value (a logic low, for example) its compare operation will be masked. Ternary CAM entry values are set forth below for the two examples previously described.
______________________________________ 11110000 10XXXXXX XXXXXXXX XXXXXXXX (data 0) 11111111 11000000 00000000 00000000 (mask 0) 11110000 10010101 100XXXXX XXXXXXXX (data 1) 11111111 11111111 11100000 00000000 (mask 1) ______________________________________
To better understand the present invention, and to more clearly distinguish the described embodiments from conventional CAM approaches, a conventional ternary CAM cell is set forth in FIG. 6. The conventional ternary CAM cell is designated by the general reference character 600, and is shown to include data store 602, a compare circuit 604, a mask store 606, and a mask circuit 608. Data values can be entered into the data register 602 by placing data values on a bit line pair (B and /B) and activating a data word line DWL. Similarly, mask values can be entered into the mask store 606 by placing data values on a bit line pair (B and /B) and activating a mask word line MWL. It is understood that the word lines (DWL and MWL) can be commonly coupled to a row of CAM cells and the bit line pair (B and/B) can be commonly coupled to a column of CAM cells.
The compare circuit 604 can receive the data value stored within the data store 602 by way of complementary data lines D and /D and a complementary comparand values by way of compare lines CMP and /CMP. The compare circuit 604 compares the data value and comparand value, and in the event the values are different, activates a match indication on match line M. In the particular conventional example of FIG. 6, the compare circuit 604 is an exclusive OR (XOR) or exclusive NOR (XNOR) circuit.
Unlike a conventional binary CAM cell, which would couple comparison results of a compare circuit directly to a match line, in the conventional ternary CAM cell 600, comparison results can be masked by the mask circuit 608. In the event the mask register 606 includes an active mask data bit (/M), the mask circuit 608 can prevent a comparison result from affecting the match line "MATCH."
FIG. 7 illustrates an example of a conventional store that may be used in a CAM (as item 602 or 606 in FIG. 6, as just one example). The store is designated by the general reference character 700. Complementary stored data values stored within store 700 are provided at data nodes 702-0 and 702-1. Data values can be set within the store 700 by driving a bit line pair (B and /B) to complementary data values and activating a corresponding word line WL.
FIG. 8 sets forth a conventional compare circuit 800 that may be used in a CAM (as item 604 in FIG. 6, as just one example). The compare circuit 800 can receive complementary data values (D and /D) and complementary comparand values (CMP and /CMP). An indication node 802 can be precharged to a high logic level at the beginning of a compare operation. A data value (D and /D) and comparand value (CMP and /CMP) can then be applied to the compare circuit 800. In the event the data value (D and /D) is different form the comparand value (C and /C), the indication node 802 will be discharged (or charged) to particular voltage. In the event the data value (D and /D) matches the comparand value (CMP and /CMP), the indication node 802 can remain charged (or discharged), indicating a match condition. The indication node 802 can be common to a number of CAM cells of the same row. Thus, an indication node 802 that remains precharged (or discharged) after a match operation can indicate a match between a row of comparand values and a row of data values (i.e., function as a match line).
FIG. 9 is a schematic diagram illustrating the mask circuit of the ternary CAM 600 of FIG. 6. The mask circuit 900 is shown to be an n-channel metal-oxide-semiconductor (MOS) transistor N900 that can have a source-drain path in series with a compare circuit, such as that set forth in FIG. 8. The gate of transistor N900 can be driven by a mask signal /M.
As noted above, some CAM applications can be met with binary CAMs while other applications can be met with ternary CAMs. Further, ternary CAMs can essentially operate in a binary mode by setting all mask values to "1." However, to place a conventional ternary CAM into a binary mode can require a number of mask value write operations. This can require valuable time to accomplish.
There may also be some CAM applications that can require both fixed and variable comparand value matching. Such applications can be met my employing a binary and ternary CAM, or alternatively, a ternary CAM having set portions with mask values that are programmed to "1." The first solution can be costly to implement and consume more space on a circuit board. The latter solution can include write operations that can consume valuable time.
It would be desirable to arrive at some sort of CAM device that can provide for rapid switching between a binary mode of operation and a ternary mode of operation.
Because a typical CAM can include a number of CAM cells arranged into an array, it can be desirable to keep CAM cells as small as possible. Increases in cell size can translate into substantial increases in overall CAM array size. Accordingly, while it can be desirable to provide a CAM having a binary and ternary mode of operation, it can be further desirable to provide such a CAM with a cell size that is not substantially larger than the size of conventional ternary CAM cells.